1. Field of the Invention
The present invention relates to a scheme for fast realization of encryption, decryption and authentication which is suitable for data concealment and communicating individual authentication in communications for a digital TV, a pay-per-view system of the satellite broadcast, a key distribution in the information distribution, electronic mails, electronic transactions, etc.
2. Description of the Background Art
In recent years, in the field of communications, various types of cryptographic techniques have been proposed because the cryptographic technique can be effectively used for the protection of secrecy between communicating parties such as the concealment of information to be transmitted. The performances of such a cryptographic technique can be evaluated in terms of the security level of cryptosystem and the speed of encryption/decryption. Namely, the cryptosystem for which the security level is high and the encryption/decryption speed is high is a superior cryptosystem.
Among such cryptographic techniques, there is a type of public key cryptosystem that uses the modular exponent calculations, known as RSA (Rivest Shamir Adleman) cryptosystem, which is already in practical use. In this RSA cryptosystem, it has been shown that the plaintext can be obtained from the ciphertext if the prime factoring of the public key can be made (see R. Rivest, A. Shamir and L. Adleman; xe2x80x9cA method for obtaining digital signatures and public-key cryptosystemsxe2x80x9d, Comm. ACM, Vol. 21, No. 2, pp. 120-126 (1978)).
The public key cryptosystem such as RSA cryptosystem has its security based on the computational difficulty for obtaining the secret key from the public key which is a publicly disclosed information, so that the security level can be increased as much when a size of the public key is increased. On the other hand, the RSA cryptosystem has been associated with a drawback that it requires a considerable amount of time for encryption/decryption because it carries out higher degree modular exponent calculations and therefore the required amount of calculations is large.
The encryption/decryption can be made faster by reducing the degree of the modular exponent calculations, for example, but that will require the reduction of the size of the public key and that in turn causes the lowering of the cryptosystem security.
In the following, the RSA cryptosystem will be described in further detail.
First, mutually different arbitrary prime numbers p and q are set as the first secret key, and the first public key n is obtained as:
n=pq
while the least common multiple L of (pxe2x88x921) and (qxe2x88x921) is obtained as:
L=1 cm(pxe2x88x921, qxe2x88x921).
Then, an arbitrary integer e is set as the second public key, and the second secret key d given by:
edxe2x89xa11(mod L)
is obtained using the Euclidean division algorithm.
Then, a plaintext M and its ciphertext C can be expressed as follow:
Cxe2x89xa1Me(mod n),
Mxe2x89xa1Cd(mod n).
Here, the value of the second public key e can be rather small like 13, for instance, so that the encryption processing can be made very fast, but the value of the second secret key d has a size nearly equal to n so that the decryption processing will be quite slow.
On the other hand, the processing amount of the modular exponent calculations is proportional to the cube of the size of a number, so that by utilizing this property, the Chinese remainder theorem can be used in order to make the decryption processing faster.
The decryption processing using the Chinese remainder theorem proceeds as follows.
dpxe2x89xa1d(mod pxe2x88x921),
dqxe2x89xa1d(mod qxe2x88x921),
uqxe2x89xa11(mod p),
Mpxe2x89xa1Cdp(mod p),
Mqxe2x89xa1Cdq(mod q),
Mxe2x89xa1((Mpxe2x88x92Mq)u(mod p))q+Mq,
where u is an inverse of q modulo p.
Here, the size of each of p, q, dp and dq is a half of the size of n so that the modular exponent calculations module p or q can be processed eight times faster, and as a result, the decryption processing as a whole can be made four times faster.
Also, the RSA cryptosystem can be easily cryptoanalyzed if the prime factoring of n can be made. Currently, the potentially threatening prime factoring algorithms include the number field sieve method and the elliptic curve method.
The required amount of calculations is of a quasi-exponential order of the size of n in the number field sieve method and of a quasi-exponential order of the size of a prime number in the elliptic curve method. The elliptic curve method is practically not a problem because of its high order calculations and large coefficients. On the other hand, the number field sieve method has a record for the prime factoring of the largest number realized so far, which is about 140 figures in decimal. Consequently, attacks using these methods are not threatening in practice if n is 1024 bits or so.
In addition, there are cases where a public key cryptosystem apparatus can be used as an authentication apparatus by reversing the public key and secret key calculations in general.
It is therefore an object of the present invention to provide a new scheme for encryption, decryption and authentication which is capable of overcoming the problems associated with the conventionally known RSA cryptosystem as described above.
More specifically, objects of the present invention are:
(1) to realize an encryption/decryption scheme which has the same security level compared with the known RSA cryptosystem on rational integer ring,
(2) to realize an encryption/decryption scheme for which the encryption/decryption processing is faster than the conventional RSA cryptosystem,
(3) to realize an encryption/decryption scheme which can also be utilized as an authentication scheme such that a single apparatus can be used for both the cipher communications and the authentication, and
(4) to realize an authentication scheme for which the authenticator generation and the verification are faster than the known authentication scheme based on the conventional RSA cryptosystem.
According to one aspect of the present invention there is provided an encryption method, comprising the steps of: setting N (xe2x89xa72) prime numbers p1, p2, . . . , pN as a first secret key, and a product p1k1p2k2 . . . pNkN as a first public key n, where k1, k2, . . . , kN are arbitrary positive integers; determining a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, using the first secret key; and obtaining a ciphertext C from a plaintext M according to:
Cxe2x89xa1Me(mod n)
using the first public key n and the second public key e.
According to another aspect of the present invention there is provided a decryption method for decrypting a ciphertext C obtained from a plaintext M according to:
xe2x80x83Cxe2x89xa1Me(mod n)
using a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, the method comprising the steps of: obtaining residues Mp1k1, Mp2k2, . . . , MpNkN modulo p1k1, p2k2, . . . , pNkN respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN; and recovering the plaintext M by applying Chinese remainder theorem to the residues Mp1k1, Mp2k2, . . . , MpNkN.
According to another aspect of the present invention there is provided an authentication method for authenticating an authentication message sent from a sender to a receiver, comprising the steps of: (a) setting at the sender side a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921; (b) obtaining at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; (c) obtaining at the sender side an encrypted authenticator S of the authenticator h(M) according to:
xe2x80x83h(M)xe2x89xa1Se(mod n)
by obtaining residues Sp1k1, Sp2k2, . . . , SpNkN modulo p1k1, p2k2, . . . , pNkN, respectively, of the encrypted authenticator S using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN, and applying Chinese remainder theorem to the residues Sp1k1, Sp2k2, . . . , SpNkN; (d) sending the encrypted authenticator S and the authentication message M from the sender to the receiver; (e) obtaining at the receiver side a first authenticator h(M)1 by calculating Se (mod n) from the encrypted authenticator S received from the sender using the second public key e; (f) obtaining at the receiver side a second authenticator h(M)2 by hashing the authentication message M received from the sender using the hash function h; and (g) judging an authenticity of the authentication message M at the receiver side by checking whether the first authenticator h(M)1 and the second authenticator h(M)2 coincide or not.
According to another aspect of the present invention there is provided an encryption apparatus, comprising: an encryption/decryption key generation processing unit for setting N (xe2x89xa72) prime numbers p1, p2, . . . , pN as a first secret key, and a product p1k1p2k2 . . . pNkN as a first public key n, where k1, k2, . . . , kN are arbitrary positive integers, and determining a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, using the first secret key; and an encryption processing unit for obtaining a ciphertext C from a plaintext M according to:
xe2x80x83Cxe2x89xa1Me(mod n)
using the first public key n and the second public key e.
According to another aspect of the present invention there is provided a decryption apparatus for decrypting a ciphertext C obtained from a plaintext M according to:
Cxe2x89xa1Me(mod n)
using a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, the apparatus comprising: a calculation processing unit for obtaining residues Mp1k1, Mp2k2, . . . , MpNkN modulo p1k1, p2k2, . . . , pNkN, respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN; and a decryption processing unit for recovering the plaintext M by applying Chinese remainder theorem to the residues Mp1k1, Mp2k2, . . . , MpNkN.
According to another aspect of the present invention there is provided a cipher communication system, comprising: a sender apparatus having: an encryption/decryption key generation processing unit for setting N (xe2x89xa72) prime numbers p1, p2, . . . , pN as a first secret key, and a product p1k1p2k2 . . . pNkN as a first public key n, where k1, k2, . . . , kN are arbitrary positive integers, and determining a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, using the first secret key; and an encryption processing unit for obtaining a ciphertext C from a plaintext M according to:
Cxe2x89xa1Me(mod n)
using the first public key n and the second public key e; and a receiver apparatus having: a calculation processing unit for obtaining residues Mp1k1, Mp2k2, . . . , MpNkN modulo p1k1, p2k2, . . . , pNkN respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN; and a decryption processing unit for recovering the plaintext M by applying Chinese remainder theorem to the residues Mp1k1, Mp2k2, . . . , MpNkN.
According to another aspect of the present invention there is provided an authentication message sender apparatus for use in authenticating an authentication message sent from a sender to a receiver, the apparatus comprising: an encryption/decryption key generation processing unit for setting at the sender side a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921; an authentication message hashing processing unit for obtaining at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; and an authenticator encryption processing unit for obtaining at the sender side an encrypted authenticator S of the authenticator h(M) according to:
h(M)xe2x89xa1Se(mod n)
by obtaining residues Sp1k1, Sp2k2, . . . , SpNkN modulo p1k1, p2k2, . . . , pNkN, respectively, of the encrypted authenticator S using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN, and applying Chinese remainder theorem to the residues Sp1k1, Sp2k2, . . . , SpNkN, and then sending the encrypted authenticator S and the authentication message M to the receiver.
According to another aspect of the present invention there is provided an authentication message receiver apparatus for use in authenticating an authentication message sent from a sender to a receiver, using a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, the apparatus comprising: an authenticator decryption processing unit for obtaining a first authenticator h(M)1 by calculating Se (mod n) from an encrypted authenticator S received from the sender using the second public key e; an authentication message hashing processing unit for obtaining a second authenticator h(M)2 by hashing an authentication message M received from the sender using a hash function h; and an authenticity verification processing unit for judging an authenticity of the authentication message M at the receiver side by checking whether the first authenticator h(M)1 and the second authenticator h(M)2 coincide or not.
According to another aspect of the present invention there is provided an authentication system for authenticating an authentication message sent from a sender to a receiver, the system comprising: a sender apparatus having: an encryption/decryption key generation processing unit for setting at the sender side a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921; an authentication message hashing processing unit for obtaining at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; and an authenticator encryption processing unit for obtaining at the sender side an encrypted authenticator S of the authenticator h(M) according to:
h(M)xe2x89xa1Se(mod n)
by obtaining residues Sp1k1, Sp2k2, . . . , SpNkN modulo p1k1, p2k2, . . . , pNkN, respectively, of the encrypted authenticator S using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN, and applying Chinese remainder theorem to the residues Sp1k1, Sp2k2, . . . , SpNkN, and then sending the encrypted authenticator S and the authentication message M to the receiver; and a receiver apparatus having: an authenticator decryption processing unit for obtaining a first authenticator h(M)1 by calculating Se (mod n) from the encrypted authenticator S received from the sender using the second public key e; an authentication message hashing processing unit for obtaining a second authenticator h(M)2 by hashing the authentication message M received from the sender using the hash function h; and an authenticity verification processing unit for judging an authenticity of the authentication message M by checking whether the first authenticator h(M)1 and the second authenticator h(M)2 coincide or not.
According to another aspect of the present invention there is provided a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an encryption apparatus, the computer readable program code means includes: first computer readable program code means for causing said computer to set N (xe2x89xa72) prime numbers p1, p2, . . . , pN as a first secret key, and a product p1k1p2k2 . . . pNkN as a first public key n, where k1, k2, . . . , kN are arbitrary positive integers, and determining a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, using the first secret key; and second computer readable program code means for causing said computer to obtain a ciphertext C from a plaintext M according to:
Cxe2x89xa1Me(mod n)
using the first public key n and the second public key e.
According to another aspect of the present invention there is provided a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a decryption apparatus for decrypting a ciphertext C obtained from a plaintext M according to:
Cxe2x89xa1Me(mod n)
using a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, the computer readable program code means includes: first computer readable program code means for causing said computer to obtain residues Mp1k1, Mp2k2, . . . , MpNkN modulo p1k1, p2k2, . . . , pNkN, respectively, of the plaintext M using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN; and second computer readable program code means for causing said computer to recover the plaintext M by applying Chinese remainder theorem to the residues Mp1k1, Mp2k2, . . . , MpNkN.
According to another aspect of the present invention there is provided a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message sender apparatus for use in authenticating an authentication message sent from a sender to a receiver, the computer readable program code means includes: first computer readable program code means for causing said computer to set at the sender side a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921; second computer readable program code means for causing said computer to obtain at the sender side an authenticator h(M) by hashing the authentication message M using a hash function h; and third computer readable program code means for causing said computer to obtain at the sender side an encrypted authenticator S of the authenticator h(M) according to:
h(M)xe2x89xa1Se(mod n)
by obtaining residues Sp1k1, Sp2k2, . . . , SpNkN modulo p1k1, p2k2, . . . , pNkN, respectively, of the encrypted authenticator S using a prescribed loop calculation with respect to the first secret key p1, p2, . . . , pN, and applying Chinese remainder theorem to the residues Sp1k1, Sp2k2, . . . , SpNkN, and then sending the encrypted authenticator S and the authentication message M to the receiver.
According to another aspect of the present invention there is provided a computer usable medium having computer readable program code means embodied therein for causing a computer to function as an authentication message receiver apparatus for use in authenticating an authentication message sent from a sender to a receiver, using a first secret key given by N (xe2x89xa72) prime numbers p1, p2, . . . , pN, a first public key n given by a product p1k1p2k2 . . . pNkN where k1, k2, . . . , kN are arbitrary positive integers, a second public key e and a second secret key d which satisfy:
edxe2x89xa11(mod L)
where L is a least common multiple of p1xe2x88x921, p2xe2x88x921, . . . , pNxe2x88x921, the computer readable program code means includes: first computer readable program code means for causing said computer to obtain a first authenticator h(M)1 by calculating Se (mod n) from an encrypted authenticator S received from the sender using the second public key e; second computer readable program code means for causing said computer to obtain a second authenticator h(M)2 by hashing an authentication message M received from the sender using a hash function h; and third computer readable program code means for causing said computer to judge an authenticity of the authentication message M at the receiver side by checking whether the first authenticator h(M)1 and the second authenticator h(M)2 coincide or not.
Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.